class Solution {
    int left, right, _n;
    string path;
    vector<string> ret;

public:
    vector<string> generateParenthesis(int n) {
        _n = n;
        dfs();
        return ret;
    }

    void dfs()
    {
        if(path.size() == 2 * _n)
        {
            ret.push_back(path);
            return;
        }

        if(left < _n)
        {
            path += '(';
            ++left;
            dfs();
            path.pop_back();
            --left;
        }
        if(right < left)
        {
            path += ')';
            ++right;
            dfs();
            path.pop_back();
            --right;
        }
    }
};